package org.lyc.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 单词拆分
 * https://leetcode.cn/problems/word-break/
 *
 * @author Liu Yicong
 * @date 2024/2/29
 */
public class IWordBreak {

	static String s1 = "leetcode";

	static String[] dict1 = {"leet", "code"};

	static String s2 = "applepenapple";

	static String[] dict2 = {"apple", "pen"};

	static String s3 = "catsandog";

	static String[] dict3 = {"cats", "dog", "sand", "and", "cat"};

	public static void main(String[] args) {
		System.out.println(wordBreak(s1, Arrays.asList(dict1)));
		System.out.println(wordBreak(s2, Arrays.asList(dict2)));
		System.out.println(wordBreak(s3, Arrays.asList(dict3)));
	}

	public static boolean wordBreak(String s, List<String> wordDict) {
		int n = s.length();
		boolean[] dp = new boolean[n];
		//遍历s的每一个字母
		for (int i = 0; i < n; i++) {
			//遍历dict中的每一个单词
			for (int j = 0; j < wordDict.size(); j++) {
				//当前的单词
				String current = wordDict.get(j);
				int length = current.length();
				if (length > i + 1) {
					continue;
				}
				//尾部匹配的单词, 如: catsandog, 当i=6时, current="sand", 则tail="sand"
				String tail = s.substring(i - length + 1, i + 1);
				//找到第一个匹配的单词的条件
				if (i - length != -1 && !dp[i - length]) {
					continue;
				}
				if (tail.equals(current)) {
					dp[i] = true;
					break;
				}
			}
		}

		return dp[n - 1];
	}
}
